package simpledb;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

/**
使用一个自定义的数据结构来执行页面的LRU回收策略
原理：每个节点存储一个LinkedNode,当get()操作时，表明时最新调用该page,置于头节点
当容量超过capacity时，删除最末尾节点（也就是最少使用的节点）,将新节点插入链表头
 */
public class LRUCache {
    //LinkedNode  双向链表中的节点，包含pre,post前后两个指针，
    class LinkedNode{
        PageId pageId;
        Page page;
        LinkedNode pre;
        LinkedNode post;

        public LinkedNode() {
        }

        public LinkedNode(PageId pageId, Page page) {
            this.pageId = pageId;
            this.page = page;
        }
    }
    //capacity双向链表的大小，也就是缓存的容量
    private int capacity;
    //当前的page数量
    private int count;
    //设head，tail两个虚节点方便操作增加删除
    private LinkedNode head;
    private LinkedNode tail;
    //用一个map存储id->page的映射关系
    private ConcurrentMap<PageId,LinkedNode> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        this.cache = new ConcurrentHashMap<PageId,LinkedNode>();
        this.head = new LinkedNode();
        head.pre = null;
        this.tail = new LinkedNode();
        tail.post = null;
        head.post = tail;
        tail.pre = head;
    }

    public boolean hasPageById(PageId pageId) {
        return cache.containsKey(pageId);
    }

    //获取一个页面，被调用时该页面置于链表头
    public Page get(PageId key)
    {
        LinkedNode node = cache.get(key);
        if(node==null)
        {
            return null;
        }
        moveHead(node);
        return node.page;
    }

    public Page getPageById(PageId pageId)
    {
        return cache.get(pageId).page;
    }


    //存入一个页面
    //当容量大于capacity时，删除链表最末尾节点
    //NO STEAL 不能回收一个dirty页面。只有当事务提交时才能将页面写回磁盘
    //当所有页面都是dirty不能被回收时，抛出DbException
    public void put(PageId pageId,Page page) throws DbException {
        LinkedNode node = cache.get(pageId);
        if(node!=null)
        {
            removeNode(node);
            moveHead(node);
            return ;
        }
        node = new LinkedNode(pageId,page);
        if(count<capacity)
        {
            cache.put(pageId,node);
            moveHead(node);
            count++;
        }
        else
        {
            LinkedNode toRemove = tail.pre;
            while(toRemove.page.isDirty()!=null)
            {
                if(toRemove==head)
                    throw new DbException("缓冲区所有页面dirty无法回收");
                toRemove = toRemove.pre;
            }
            cache.remove(toRemove.pageId);
            popTail();
            cache.put(pageId,node);
            moveHead(node);
        }

    }

    //删除末尾节点
    private void popTail() {
        LinkedNode last = tail.pre;
        removeNode(last);
        cache.remove(last.pageId);
    }

    //实际的节点操作
    private void removeNode(LinkedNode node) {
        LinkedNode before = node.pre;
        LinkedNode after = node.post;
        before.post = after;
        after.pre = before;
    }

    //将节点置于链表头
    public void moveHead(LinkedNode node)
    {
        if(head.post == node)
            return;
        node.post = head.post;
        head.post = node;
        node.post.pre = node;
        node.pre = head;
    }

    public ConcurrentMap<PageId, LinkedNode> getCache() {
        return cache;
    }
}
